# -*- coding: utf-8 -*
__author__ = 'dell'
import math
import copy
import random
from itertools import *
from operator import itemgetter, attrgetter

inputA = open('1.txt', 'r') #网点经纬度
inputB = open('2.txt', 'r') #配送点经纬度
inputF = open('4.txt', 'r') #电商订单
output = open('staticCycle.txt', 'w') #输出环路安排表
A={}
B={}
F=[]
packetLimit = 140
for eachline in inputA.readlines():
    temp = eachline.strip().split(',')
    A[temp[0]] = [float(temp[1]),float(temp[2])]

for eachline in inputB.readlines():
    temp = eachline.strip().split(',')
    B[temp[0]] = [float(temp[1]),float(temp[2])]

def calAngle(A_id,B_id):
    dx = B[B_id][0]-A[A_id][0]
    dy = B[B_id][1]-A[A_id][1]
    if dx>0 and dy>=0:
        angle = math.atan(dy/dx)
    elif dx==0 and dy>0:
        angle = math.pi/2
    elif dx<0 and dy>=0:
        angle = math.pi-math.atan(dy/-dx)
    elif dx<0 and dy<0:
        angle = math.pi+math.atan(dy/dx)
    elif dx==0 and dy<0:
        angle = math.pi/2*3
    elif dx>0 and dy<0:
        angle = 2*math.pi-math.atan(-dy/dx)
    else:pass
    return angle


for eachline in inputF.readlines():
    temp = eachline.strip().split(',')
    angle = calAngle(temp[2],temp[1])
    A_num = int(temp[2].strip('A'))
    F.append([A_num,angle,temp[0],temp[1],temp[2],int(temp[3])]) #F_id,B_id,A_id,Num

def caldistance(point1,point2):
    dlon = (point1[0]-point2[0])/2
    dlat = (point1[1]-point2[1])/2
    lat1 = point1[1]
    lat2 = point2[1]
    R = 6378137
    s= 2*R*math.asin(((math.sin(dlat*math.pi/180))**2+math.cos(lat1*math.pi/180)*math.cos(lat2*math.pi/180)*(math.sin(dlon*math.pi/180))**2)**0.5)
    return s

def calCycleValue(A_id,B_cycle):
    distance = caldistance(A[A_id],B[B_cycle[0]])
    for i in range(len(B_cycle)-1):
        distance += caldistance(B[B_cycle[i]],B[B_cycle[i+1]])
    return distance

def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体
    px = len(pop)
    bestindividual = copy.deepcopy(pop[0])
    bestfit = fitvalue[0]
    for i in range(1,px):
        if(fitvalue[i] > bestfit):
            bestfit = fitvalue[i]
            bestindividual = copy.deepcopy(pop[i])

    return [bestindividual, bestfit]



def sum(fitvalue):
    total = 0
    for i in range(len(fitvalue)):
        total += fitvalue[i]
    return total

def cumsum(fitvalue):
    for i in range(len(fitvalue)):
        t = 0
        j = 0
        while(j <= i):
            t += fitvalue[j]
            j = j + 1
        fitvalue[i] = t

def selection(pop, fitvalue): #自然选择（轮盘赌算法）
    newfitvalue = []
    totalfit = sum(fitvalue)
    for i in range(len(fitvalue)):
        newfitvalue.append(fitvalue[i] / totalfit)
    cumsum(newfitvalue)
    ms = []
    poplen = len(pop)
    for i in range(poplen):
        ms.append(random.random()) #random float list ms
    ms.sort()
    fitin = 0
    newin = 0
    newpop = copy.deepcopy(pop)
    while newin < poplen:
        if(ms[newin] < newfitvalue[fitin]):
            newpop[newin] = pop[fitin]
            newin = newin + 1
        else:
            fitin = fitin + 1
    pop = copy.deepcopy(newpop)


def calobjvalue(pop,Aname):
    popValue =[]
    for eachone in pop:
        value = -calCycleValue(Aname,eachone)
        popValue.append(value)
    return popValue


def crossover(pop, pc): #个体间交叉，实现基因交换
    poplen = len(pop)
    for i in range(poplen):
        if(random.random() < pc):
            cpoint = random.randint(0,len(pop[0])-2)
            pop[i] = copy.deepcopy(pop[i][cpoint:])+copy.deepcopy(pop[i][0:cpoint])

def mutation(pop, pm):
    poplen = len(pop)
    for i in range(poplen):
        if(random.random() < pm):
            point1 = random.randint(1,len(pop[0])-2)
            point2 = random.randint(point1,len(pop[0])-1)
            temp1 = copy.deepcopy(pop[i][point1])
            temp2 = copy.deepcopy(pop[i][point2])
            pop[i][point1] = copy.deepcopy(temp2)
            pop[i][point2] = copy.deepcopy(temp1)

def sortEachCycle(cycle):
    # 全排列+遗传算法
    newcycle = cycle[:]
    value = calCycleValue(cycle[0],cycle[1:])

    if len(cycle[1:])<6:#全排列
        for i in permutations(cycle[1:]):
            if calCycleValue(cycle[0],i)<value:
                newcycle = cycle[0:1]+list(i)
                value = calCycleValue(cycle[0],i)

    else:#遗传算法
        popSize=100
        popIndivudual =[cycle[1:] for i in range(popSize)]
        results =[]
        pc = 0.5
        pm = 0.3
        for i in range(50):
            fitvalue = calobjvalue(popIndivudual,cycle[0]) #计算目标函数值
            [bestindividual, bestfit] = best(popIndivudual, fitvalue) #选出最好的个体和最好的函数值
            #print bestindividual
            results.append([bestfit,bestindividual]) #每次繁殖，将最好的结果记录下来
            selection(popIndivudual, fitvalue) #自然选择，淘汰掉一部分适应性低的个体
            crossover(popIndivudual, pc) #交叉繁殖
            mutation(popIndivudual, pm) #基因突变
        results.sort()
        newcycle=cycle[0:1]+copy.deepcopy(results[-1][1])
    return newcycle


def calCycle(subSetF):
    Aname = subSetF[0][4]
    newsubSetF = sorted(subSetF,key=itemgetter(3))
    Bnumber=len(subSetF)
    BtoA={}
    Blimit = {}
    BtoB=[]
    oneCycle = []
    packetSet = []
    for k in range(len(newsubSetF)):
        BtoA[newsubSetF[k][3]] = caldistance(A[Aname],B[newsubSetF[k][3]])
        Blimit[newsubSetF[k][3]] = 0
        oneCycle.append([newsubSetF[k][3]])
        packetSet.append(newsubSetF[k][-1])

    for i in range(len(newsubSetF)-1):
        for j in range(i+1,len(subSetF)):
            S = BtoA[newsubSetF[j][3]]+BtoA[newsubSetF[i][3]]-caldistance(B[newsubSetF[j][3]],B[newsubSetF[i][3]])
            BtoB.append([S,newsubSetF[i][3],newsubSetF[j][3]])
    BtoB.sort(reverse=True)
    while len(BtoB)>0:
        cycle1=0
        cycle2=0
        for i in range(len(oneCycle)):
            cycleLength = len(oneCycle[i])
            if cycleLength==1:
                if oneCycle[i][0]==BtoB[0][1]:cycle1=i
                if oneCycle[i][0]==BtoB[0][2]:cycle2=i
            else:
                if oneCycle[i][0]==BtoB[0][1]:cycle1=[i,0]
                if oneCycle[i][-1]==BtoB[0][1]:cycle1=[i,-1]
                if oneCycle[i][0]==BtoB[0][2]:cycle2=[i,0]
                if oneCycle[i][-1]==BtoB[0][2]:cycle2=[i,-1]

        if type(cycle1)==int and type(cycle2)==int:
            if packetSet[cycle1]+packetSet[cycle2]<=140:
                oneCycle[cycle1] =oneCycle[cycle1]+oneCycle[cycle2]
                packetSet[cycle1] +=packetSet[cycle2]
                oneCycle.pop(cycle2)
                packetSet.pop(cycle2)
                Blimit[BtoB[0][1]] +=1
                Blimit[BtoB[0][2]] +=1
            else:pass

        if type(cycle1)==list and type(cycle2)==int:
            if cycle1[1]==0 and packetSet[cycle1[0]]+packetSet[cycle2]<=140:
                oneCycle[cycle1[0]] = oneCycle[cycle2][:]+oneCycle[cycle1[0]][:]
                packetSet[cycle1[0]] +=packetSet[cycle2]
                oneCycle.pop(cycle2)
                packetSet.pop(cycle2)
                Blimit[BtoB[0][1]] +=1
                Blimit[BtoB[0][2]] +=1
            if cycle1[1]==-1 and packetSet[cycle1[0]]+packetSet[cycle2]<=140:
                oneCycle[cycle1[0]] = oneCycle[cycle1[0]][:]+oneCycle[cycle2][:]
                packetSet[cycle1[0]] +=packetSet[cycle2]
                oneCycle.pop(cycle2)
                packetSet.pop(cycle2)
                Blimit[BtoB[0][1]] +=1
                Blimit[BtoB[0][2]] +=1

        if type(cycle1)==int and type(cycle2)==list:
            if cycle2[1]==0 and packetSet[cycle2[0]]+packetSet[cycle1]<=140:
                oneCycle[cycle2[0]] = oneCycle[cycle1][:]+oneCycle[cycle2[0]][:]
                packetSet[cycle2[0]] +=packetSet[cycle1]
                oneCycle.pop(cycle1)
                packetSet.pop(cycle1)
                Blimit[BtoB[0][1]] +=1
                Blimit[BtoB[0][2]] +=1
            if cycle2[1]==-1 and packetSet[cycle2[0]]+packetSet[cycle1]<=140:
                oneCycle[cycle2[0]] = oneCycle[cycle2[0]][:]+oneCycle[cycle1][:]
                packetSet[cycle2[0]] +=packetSet[cycle1]
                oneCycle.pop(cycle1)
                packetSet.pop(cycle1)
                Blimit[BtoB[0][1]] +=1
                Blimit[BtoB[0][2]] +=1

        if type(cycle1)==list and type(cycle2)==list and cycle1[0]!=cycle2[0]:
            if packetSet[cycle2[0]]+packetSet[cycle1[0]]<=140:
                if cycle1[1]==0 and cycle2[1]==0:
                    oneCycle[cycle2[0]].reverse()
                    oneCycle[cycle1[0]] = oneCycle[cycle2[0]][:]+oneCycle[cycle1[0]][:]
                    packetSet[cycle1[0]] +=packetSet[cycle2[0]]
                    oneCycle.pop(cycle2[0])
                    packetSet.pop(cycle2[0])
                    Blimit[BtoB[0][1]] +=1
                    Blimit[BtoB[0][2]] +=1
                if cycle1[1]==-1 and cycle2[1]==-1:
                    oneCycle[cycle2[0]].reverse()
                    oneCycle[cycle1[0]] = oneCycle[cycle1[0]][:]+oneCycle[cycle2[0]][:]
                    packetSet[cycle1[0]] +=packetSet[cycle2[0]]
                    oneCycle.pop(cycle2[0])
                    packetSet.pop(cycle2[0])
                    Blimit[BtoB[0][1]] +=1
                    Blimit[BtoB[0][2]] +=1
                if cycle1[1]==0 and cycle2[1]==-1:
                    oneCycle[cycle1[0]] = oneCycle[cycle2[0]][:]+oneCycle[cycle1[0]][:]
                    packetSet[cycle1[0]] +=packetSet[cycle2[0]]
                    oneCycle.pop(cycle2[0])
                    packetSet.pop(cycle2[0])
                    Blimit[BtoB[0][1]] +=1
                    Blimit[BtoB[0][2]] +=1
                if cycle1[1]==-1 and cycle2[1]==0:
                    oneCycle[cycle1[0]] = oneCycle[cycle1[0]][:]+oneCycle[cycle2[0]][:]
                    packetSet[cycle1[0]] +=packetSet[cycle2[0]]
                    oneCycle.pop(cycle2[0])
                    packetSet.pop(cycle2[0])
                    Blimit[BtoB[0][1]] +=1
                    Blimit[BtoB[0][2]] +=1


        [left,right]=BtoB[0][1],BtoB[0][2]
        BtoB.pop(0)
        if Blimit[left]==2:
            deletelist=[]
            for each in BtoB:
                if each[1]==left or each[2]==left:deletelist.append(each)
            for k in deletelist:
                BtoB.remove(k)
        if Blimit[right]==2:
            deletelist=[]
            for each in BtoB:
                if each[1]==right or each[2]==right:deletelist.append(each)
            for k in deletelist:
                BtoB.remove(k)
    newCycle = []

    for eachone in oneCycle:
        newCycle.append(sortEachCycle([Aname]+eachone))


    return newCycle


    #################






Edemo = []

n=0
for i in range(1,len(A)+1):
    subSetF = []
    for j in range(n,len(F)):
        if F[j][0]==i:subSetF.append(F[j])
        else:
            n += len(subSetF)
            break

    cycleSet = calCycle(subSetF)
    print cycleSet
    for everyF in cycleSet:
        Edemo +=everyF
    for eachCycle in cycleSet:
        for eachpoint in eachCycle:
            output.write('%s\t' %eachpoint)
        output.write('\n')

inputA.close()
inputB.close()
inputF.close()
output.close()



print (len(list(set(Edemo)))-124-9214)